// run: $exec < input
#include <iostream>
#include <algorithm>

int const maxn = 17;
int const maxm = 131062;
long long const  inf = (1ll) << 44;
long long f[maxm][maxn];
long long a[maxn];
int p[maxn];
int n;

int count(int x)
{
	int ret = 0;
	for (; x; x /= 2) ret += x & 1;
	return ret;
}

void init()
{
	for (int i = 0; i <= (1 << n); i++)
		for (int j = 0; j <= n; j++)
			f[i][j] = -inf;
}

int main()
{
	std::ios::sync_with_stdio(false);
	int T; std::cin >> T;
	for (int ti = 1; ti <= T; ti++) {
		std::cout << "Case #" << ti << ":\n";
		std::cin >> n;
		init();
		for (int i = 0; i < n; i++) std::cin >> a[i] >> p[i];

		for (int i = 0; i < n; i++)
			if (p[i] == -1 || !p[i]) f[1 << i][i] = 0;
		for (int i = 1; i < (1 << n); i++) {
			int one = count(i);
			if (one == 1) continue;
			for (int j = 0; j < n; j++) {
				if (!((i >> j) & 1)) continue;
				if (p[j] != -1 && p[j] + 1 != one) continue;
				int ts = i ^ (1 << j);
				for (int t = 0; t < n; t++) {
					if (!((ts >> t) & 1)) continue;
					if (p[t] != -1 && p[t] != one - 2) continue;
					f[i][j] = std::max(f[i][j], f[ts][t] + a[t] * a[j]);
				}
			}
		}
		long long ans = -inf;
		for (int i = 0; i < n; i++)
			ans = std::max(ans, f[(1 << n) - 1][i]);
		std::cout << ans << '\n';
	}
}

